A
angle brackets (< and >)
C
class template
class template header
F
formal parameter in a function template definition
friend
function template
K
 keyword class
keyword template
N
non-type parameter
O
overloading template functions
P
parameterized type
S
static
static data member
T
 template
template class
template function
type parameter
typename

Behind that outside pattern the dim shapes get clearer every day. It is always the same shape, only very numerous.
Charlotte Perkins Gilman

 If you are able to slip through the parameters of the skies and the earth, then do so.
The Koran

 A Mighty Maze! but not without a plan.
Alexander Pope
Fig. 12.1 A function template.
Fig. 12.2 Using template functions.
Fig. 12.3 Demonstrating class template Stack.
Fig. 12.4 Passing a Stack template object to a function template.
Answer 12.1
a) False. It could be a non-template function.
b) False. Each template class will have a copy of the static data member.
c) True.
d) False. Formal parameter names among template functions need not be unique.
e) False. Keyword class in this context also allows for a type parameter of a built- in type.

 Answer 12.2
a) template functions, template classes.
b) template, angle brackets (< and >).
c) overloading.
d) parameterized.
e) binary scope resolution.
f) file.

 Answer 12.9
A function template is used to instantiate template functions.

 Answer 12.14
If the compiler cannot match the function call made to a template or if the matching process results in multiple matches at compile time, the compiler generates an error.

 Answer 12.15
When creating template classes from a class template, it is necessary to provide a type (or possibly several types) to complete the definition of the new type being declared. For example, when creating an "array of integers" from an Array class template, the type int is provided to the class template to complete the definition of an array of integers.

 Answer 12.19
To specify at compile time the size of the container class object being declared.

 Answer 12.23
For static members of a class template, each template class instantiated receives its own copy of all the static members. Then all objects instantiated for a given template class access that particular template class's static members.

 Answer 12.3
The solution to this exercise can be found on your Cyber Classroom CD. Copy the file cpphtp2/answers/P12_03.zip to your hard drive and unzip the program code.

 Answer 12.7
The solution to this exercise can be found on your Cyber Classroom CD. Copy the file cpphtp2/answers/P12_07.zip to your hard drive and unzip the program code.
Exercise 12.1
Answer each of the following true or false. For those that are false, state why.
a) A friend function of a function template must be a template function.
b) If several template classes are generated from a single class template with a single static data member, each of the template classes shares a single copy of the class template's static data member.
c) A template function can be overloaded by another template function with the same function name.
d) The name of a formal parameter can be used only once in the formal parameter list of the template definition. Formal parameter names among template definitions must be unique.
 e) Keyword class as used with a template type parameter specifically means "any user-defined class type."

 Exercise 12.2
Fill in the blanks in each of the following:
a) Templates enable us to specify, with a single code segment, an entire range of related functions called ________ , or an entire range of related classes called ______.
b) All function template definitions begin with the keyword ________ followed by a list of formal parameters to the function template enclosed in ________.
c) The related functions generated from a function template all have the same name, so the compiler uses ________ resolution to invoke the proper function.
d) Class templates are also called ________ types.
 e) The ________ operator is used with a template class name to tie each member function definition to the class template's scope.
f) As with static data members of non-template classes, static data members of template classes must also be initialized at ________ scope.

 Exercise 12.3
Write a function template bubbleSort based on the sort program of Fig. 5.15. Write a driver program that inputs, sorts, and outputs an int array and a float array.

 Exercise 12.4
Overload function template printArray of Fig. 12.2 so that it takes two- additional integer arguments, namely int lowSubscript and int highSubscript. A call to this function will print only the designated portion of the array. Validate lowSubscript and highSubscript; if either is out-of-range or if highSubscript is less than or equal to lowSubscript, the overloaded printArray function should return 0; otherwise, printArray should return the number of elements printed. Then modify main to exercise both versions of printArray on arrays a, b, and c. Be sure to test all capabilities of both versions of printArray.


 Exercise 12.5
Overload function template printArray of Fig. 12.2 with a non-template version that specifically prints an array of character strings in neat, tabular, column format.


 Exercise 12.6
Write a simple function template for predicate function isEqualTo that compares its two arguments with the equality operator (==) and returns 1 if they are equal and 0 if they are not equal. Use this function template in a program that calls isEqualTo only with a variety of built-in types. Now write a separate version of the program that calls isEqualTo with a user-defined class type, but does not overload the equality operator. What happens when you attempt to run this program? Now overload the equality operator (with operator function operator==). Now what happens when you attempt to run this program?


 Exercise 12.7
Use a non-type parameter numberOfElements and a type parameter elementType to help create a template for the Array class we developed in Chapter 8, "Operator Overloading." This template will enable Array objects to be instantiated with a specified number of elements of a specified element type at compile time.
 Exercise 12.8
Write a program with class template Array. The template can instantiate an Array of any element type. Override the template with a specific definition for an Array of float elements (class Array< float >). The driver should demonstrate the instantiation of an Array of int through the template, and should show that an attempt to instantiate an Array of float uses the definition provided in class Array< float >.


 Exercise 12.9
Distinguish between the terms function template and template function.

 Exercise 12.10
Which is more like a stencil--a class template or a template class? Explain your answer.


 Exercise 12.11
What is the relationship between function templates and overloading?


 Exercise 12.12
Why might you choose to use a function template instead of a macro?

 Exercise 12.13
What performance problem can result from using function templates and class templates?


 Exercise 12.14
The compiler performs a matching process to determine which template function to call when a function is invoked. Under what circumstances does an attempt to make a match result in a compile error?

 Exercise 12.15
Why is it appropriate to call a class template a parameterized type?

 Exercise 12.16
Explain why you might use the statement

Array< Employee > workerList( 100 );
in a C++ program.


 Exercise 12.17
Review your answer to Exercise 12.16. Now, why might you use the statement

Array< Employee > workerList;
in a C++ program?


 Exercise 12.18
Explain the use of the following notation in a C++ program.

template< class T > Array< T >::Array( int s )


Exercise 12.19
Why might you typically use a non-type parameter with a class template for a container such as an array or stack?

 Exercise 12.20
Describe how to provide a class for a specific type to override the class template for that type.


 Exercise 12.21
Describe the relationship between class templates and inheritance.


 Exercise 12.22
Suppose a class template has the header

template< class T1 > class C1
Describe the friendship relationships established by placing each of the following friendship declarations inside this class template header. Identifiers beginning with "f" are functions, identifiers beginning with "C" are classes, and identifiers beginning with "T" can represent any type (i.e., built-in types or class types).

a)  friend void f1();

b)  friend void f2( C1< T1 > &);

c)  friend void C2::f4();

d)  friend void C3< T1 >::f5( C1< T1 > & );



e)  friend class C5;



f)  friend class C6< T1 >;


Exercise 12.23
Suppose class template Employee has a static data member count. Suppose three template classes are instantiated from the class template. How many copies of the static data member will exist? How will the use of each be constrained (if at all)?
Templates certainly offer the benefits of software reusability. But keep in mind that multiple copies of template functions and template classes are still instantiated in a program despite the fact that the template is
written only once. These copies can consume considerable memory.

 When it is possible to do so, specifying the size of a container class (such as an array class or a stack class) at compile time (possibly through a non-type template size parameter) eliminates the execution time
overhead of creating the space dynamically with new.

Figure 12.1 A function template.



 Figure 12.2 Using template functions.



 Figure 12.3 Demonstrating class template Stack.



 Figure 12.4 Passing a Stack template object to a function template.
* To be able to use function templates to create a group of related (overloaded) functions. * To be able to distinguish between function templates and template functions. * To be able to use class templates to create a group of related types. * To be able to distinguish between class templates and template classes. * To understand how to overload template functions. * To understand the relationships among templates, friends, inheritance, and static members.
Not placing class (or the new keyword typename) before every formal type parameter of a function template.

 If a template is invoked with a user-defined class type, and if that template uses operators (like ==, +, <=, etc.) with objects of that class type, then those operators must be overloaded! Forgetting to overload such
operators causes errors because the compiler, of course, still generates calls to the appropriate overloaded operator functions despite the fact that these functions are not present.

 The compiler performs a matching process to determine what function to call when a function is invoked. If no match can be found, or if the matching process produces multiple matches, a
compiler error is generated.
Templates are one of C++'s capabilities for software reuse.

 Class templates encourage software reusability by enabling type-specific versions of generic classes to be instantiated.

 When it is possible to do so, specifying the size of a container at compile time (possibly through a non-type template size parameter) avoids the possibility of a potentially fatal execution-time error if
new is unable to obtain the needed memory.
12 Templates
12.1Introduction
12.2Function Templates
12.3Overloading Template Functions
12.4Class Templates
12.5Class Templates and Non-Type Parameters
12.6Templates and Inheritance
12.7Templates and Friends
12.8Templates and Static Members
12.9Summary
Terminology
Figures
12.1 Introduction
In this chapter we discuss one of C++'s more powerful features, namely templates. Templates enable us to specify, with a single code segment, an entire range of related (overloaded) functions--called template functions--or an entire range of related classes--called template classes.
We might write a single function template for an array sort function and then have C++ automatically generate separate template functions that will sort an int array, sort a float array, sort an array of strings, and so on.
We discussed function templates in Chapter 3. For the benefit of those readers who skipped that treatment, we present an additional discussion and example in this chapter.
We might write a single class template for a stack class and then have C++ automatically generate separate template classes such as a stack-of-int class, a stack-of- float class, a stack-of-string class, and so on.
Note the distinction between function templates and template functions: Function templates and class templates are like stencils out of which we trace shapes; template functions and template classes are like the
separate tracings that all have the same shape but could be drawn in different colors, for example.
In this chapter, we will present examples of a function template and a class template. We will also consider the relationships between templates and other C++ features such as overloading, inheritance, friends and static members.
The design and details of the template mechanisms discussed here are based on the work of Bjarne Stroustrup as presented in his paper, Parameterized Types for C++, and published in the Proceedings of the USENIX C++ Conference held in Denver, Colorado in October, 1988.
 This chapter is meant to serve only as a brief introduction to the rich and complex topic of templates. Chapter 20, "Standard Template Library (STL)," the largest chapter in this book, presents an in-depth treatment of the template container classes, iterators and algorithms of the STL. Chapter 20 contains dozens of live-code template-based examples illustrating more sophisticated template programming techniques than those used here in Chapter 12.
12.2 Function Templates
Overloaded functions are normally used to perform similar operations on different types of data. If the operations are identical for each type, this may be performed more compactly and conveniently using function templates. The programmer writes a single function template definition. Based on the argument types provided in calls to this function, the compiler automatically generates separate object-code functions to handle each type of call appropriately. In C, this task can be performed using macros created with the preprocessor directive #define (see Chapter 17, "The
Preprocessor"). However, macros present the possibility for serious side effects and do not enable the compiler to perform type checking. Function templates provide a compact solution like macros, but enable full type checking.
All function template definitions begin with the keyword template followed by a list of formal parameters to the function template enclosed in angle brackets (< and >); each formal parameter that represents a type must be preceded by the keyword class as in

template< class T >
or
 
template< class ElementType >
or

template< class BorderType, class FillType >
The formal parameters of a template definition are used (as they would be with arguments of built-in types or user-defined types) to specify the types of the arguments to the function, to specify the return type of the function, and to declare variables within the function. The function definition follows and is defined like any other function. Note that the keyword class used to specify function template type parameters actually means "any built-in type or user-defined type."
 Let us examine the printArray function template in Fig. 12.1. The function template is used in the complete program of Fig. 12.2.
The printArray function template declares a single formal parameter T (T could be any valid identifier) for the type of the array to be printed by function printArray; T is referred to as a type parameter. When the compiler detects a printArray function invocation in the program source code, the type of printArray's first argument is substituted for T throughout the template definition, and C++ creates a complete template function for printing an array of the specified data type. Then, the newly created function is compiled.
In Fig. 12.2, three printArray functions are instantiated--one expects an int array, one expects a double array, and one expects a char array. For example, the instantiation for type int is:

void printArray( const int *array, const int count )

{

   for ( int i = 0; i < count; i++ )

      cout << array[ i ] << " ";



   cout << endl;

}
Every formal parameter in a function template definition should normally appear in the function's
parameter list at least once. The name of a formal parameter can be used only once in the parameter list of a template header. Formal parameter names among template functions need not be unique.
Figure 12.2 illustrates the use of the printArray function template. The program begins by instantiating int array a, double array b, and char array c, of sizes 5, 7, and 6, respectively. Then each of the arrays is printed by calling printArray--once with a first argument a of type int *, once with a first argument b of type double *, and once with a first argument c of type char *. The call

printArray( a, aCount );
for example, causes the compiler to instantiate a printArray template function for which type parameter T is int. The call

printArray( b, bCount );
causes the compiler to instantiate a second printArray template function for which type parameter T is double. The call

printArray( c, cCount );
causes the compiler to instantiate a third printArray template function for which type parameter T is char.
 In this example, the template mechanism saves the programmer from having to write three separate overloaded functions with prototypes

void printArray( const int *, const int );

void printArray( const double *, const int );

void printArray( const char *, const int );
Select the function template definition header that is syntactically correct.
<template> (int) (*foo) (char *m[]).
template class <foo>(char *m[]).
<template><typename T>int foo(char *m[]).
<template><typename T, T2>T foo(T2 *m[]).
template<class X> void *foo(X *m[]).
12.3 Overloading Template Functions
Template functions and overloading are intimately related. The related functions generated from a function template all have the same name, so the compiler uses overloading resolution to invoke the proper function.
A function template itself may be overloaded in several ways. We can provide other function templates that specify the same function name but different function parameters. For example, the printArray function template of Fig. 12.2 could be overloaded with another printArray function template with additional parameters lowSubscript and highSubscript to specify
the portion of the array to be printed (see Exercise 12.4).
A function template can also be overloaded by providing other non-template functions with the same function name but different function arguments. For example, the printArray function template of Fig. 12.2 could be overloaded with a non-template version that specifically prints an array of character strings in neat, tabular, column format (see Exercise 12.5).
The compiler performs a matching process to determine what function to call when a function is invoked. First the compiler tries to find and use a precise match in which the function names and argument types match
perfectly with those of the function call. If this fails, the compiler checks if a function template is available that can be used to generate a template function with a precise match of function name and argument types. If such a function template is found, the compiler generates and uses the appropriate template function. Note that, until recently, this matching process with templates required precise matches on all argument types--no automatic conversions were applied. This has been relaxed so types need not match exactly--the usual overloading rules apply.
Select the true statement(s).
Function templates cannot be overloaded.
When function templates are overloaded, the compiler first attempts a match with the non-template versions of the function.
12.4 Class Templates
It is possible to understand what a stack is (a data structure into which we insert items in one order and retrieve them in last-in-first-out order) independent of the type of the items being placed in the stack. But when it comes to actually instantiating a stack, a data type must be specified. This creates a wonderful opportunity for software reusability. What we need are the means for describing the notion of a stack generically and instantiating classes that are type- specific versions of this generic class. This capability is provided by class templates in C++.
 Class templates are called parameterized types because they require one or more type parameters to specify how to customize a "generic class" template to form a specific template class.
The programmer who wishes to produce a variety of template classes simply writes one class template definition. Each time the programmer needs a new type-specific instantiation, the programmer uses a concise, simple notation and the compiler writes the source code for the template class the programmer requires. One Stack class template, for example, could thus become the basis for creating many Stack classes
(such as "Stack of double," "Stack of int," "Stack of char," "Stack of Employee," etc.) used in a program.
Note the definition of the Stack class template in Fig. 12.3. It looks like a conventional class definition except that it is preceded by the header (line 8)

template< class T >
to specify that this is a class template definition with type parameter T indicating the type of the Stack class to be created. The programmer need not specifically use identifier T--any identifier can be used. The type of element to be stored on this Stack is mentioned only generically as T throughout the Stack class header and member function definitions. We will show
momentarily how T becomes associated with a specific type, such as double or int.
Now let us consider the driver (function main) that exercises the Stack class template (see the output in Fig. 12.3). The driver begins by instantiating object doubleStack of size 5. This object is declared to be of class Stack< double > (pronounced "Stack of double"). The compiler associates type double with type parameter T in the template to produce the source code for a Stack class of type double. Although the program does not see this source code, it is included in the source code and compiled.
 The driver then successively pushes the double values 1.1, 2.2, 3.3, 4.4 and 5.5 onto doubleStack. The push loop terminates when the driver attempts to push a sixth value onto doubleStack (which is already full because it was created to hold a maximum of 5 elements).
The driver now pops the five values off the stack (note in Fig. 12.3 that the values do pop off in last-in-first-out order). The driver attempts to pop a sixth value, but doubleStack is now empty, so the pop loop terminates.
Next, the driver instantiates integer stack intStack with the declaration

Stack< int > intStack;
(pronounced "intStack is a Stack of int"). Because no size is specified, the size defaults to 10 as specified in the default constructor (line 11). Once again, the driver loops pushing values onto intStack until it is full, and then loops popping values off intStack until it is empty. Once again, the values pop off in last-in-first- out order.
The member function definitions outside the class template header each begin with the header (line 24)

template< class T >
Then each definition resembles a conventional function definition except that the Stack element type is always listed generically as type parameter T. The binary scope
resolution operator is used with the class template name Stack< T > to tie each member function definition to the class template's scope. In this case, the class name is Stack< T >. When doubleStack is instantiated to be of type Stack< double >, the Stack constructor uses new to create an array of elements of type double to represent the stack (line 29). The statement

stackPtr = new T[ size ];
in the Stack class template definition is generated by the compiler in the Stack< double > template class as

stackPtr = new double[ size ];
Notice that the code in function main of Fig. 12.3 is almost identical for both the doubleStack manipulations in the top half of main and the intStack manipulations in the bottom half of main. This presents us with another opportunity to use a function template. The program of Fig. 12.4 uses function template testStack to perform the same tasks as main in Fig. 12.3--push a series of values onto a Stack< T > and pop the values off a Stack< T >. Function template testStack uses formal parameter T to represent the data type stored in the Stack< T >. The function template takes four arguments--a reference to an object of type Stack< T >, a value of type T that will be the first value
pushed onto the Stack< T >, a value of type T used to increment the values pushed onto the Stack< T > and a character string of type const char * that represents the name of the Stack< T > object for output purposes. Function main now simply instantiates an object of type Stack< double > called doubleStack and an object of type Stack< int > called intStack and uses these objects in lines 37 and 38

testStack( doubleStack, 1.1, 1.1, "doubleStack" );

testStack( intStack, 1, 1, "intStack" );
Note that the output of Fig. 12.4 precisely matches the output of Fig. 12.3.
 Select the true statement(s).
Class templates do not require the use of the template keyword.
Class templates represent generic classes.
Class templates are parameterized types.
12.5 Class Templates and Non-Type Parameters
The Stack class template of the previous section used only type parameters in the template header. It is also possible to use non-type parameters; a non-type parameter can have a default argument, and the non- type parameter is treated as const. For example, the template header could be modified to take an int elements parameter as follows:

template< class T, int elements >  

    // note non-type parameter
Then, a declaration such as
 
Stack< double, 100 >

     mostRecentSalesFigures;
would instantiate (at compile time) a 100-element Stack template class named mostRecentSalesFigures of double values; this template class would be of type Stack< double, 100 >. The class header might then contain a private data member with an array declaration such as 

T stackHolder[ elements ];

    // array to hold stack contents
In the exercises, you will be asked to use a non-type parameter to create a template for the Array class developed in Chapter 8, "Operator Overloading." This
template will enable Array objects to be instantiated with a specified number of elements of a specified type at compile time, rather than dynamically creating space for the Array objects at execution time.
A class for a specific type that does not match a common class template can be provided to override the class template for that type. For example, an Array class template can be used to instantiate an array of any type. The programmer may choose to take control of instantiating the Array class of a specific type, such as Martian. This is done simply by forming the new class with a class name of Array<Martian>.
 Select the true statement(s).
Class templates can have non-type parameters.
Template classes that have non-type parameters with different values are considered to be different data types.
12.6 Templates and Inheritance
Templates and inheritance relate in several ways:
* A class template can be derived from a template class. * A class template can be derived from a non-template class. * A template class can be derived from a class template. * A non-template class can be derived from a class template.
12.7 Templates and Friends
We have seen that functions and entire classes can be declared as friends of non-template classes. With class templates, the obvious kinds of friendship arrangements can be declared. Friendship can be established between a class template and a global function, a member function of another class (possibly a template class), or even an entire class (possibly a template class). The notations required to establish these friendship relationships can be cumbersome.
Inside a class template for class X that has been declared with
 
template< class T  > class X
a friendship declaration of the form

friend void f1();
makes function f1 a friend of every template class instantiated from the preceding class template.
Inside a class template for class X that has been declared with

template< class T > class X
a friendship declaration of the form

friend void f2( X< T > & );
for a particular type T such as float makes function f2( X< float > & ) a friend of X< float > only.
Inside a class template, you can declare that a member function of another class is a friend of any template class generated from the class template. Simply name the member function of the other class using the class name and the binary scope-resolution operator. For example, inside a class template for class X that has been declared with

template< class T > class X
a friendship declaration of the form

friend void A::f4();
makes member function f4 of class A a friend of every template class instantiated from the preceding class template.
Inside a class template for class X that has been declared with

template< class T > class X
a friendship declaration of the form

friend void C< T >::f5( X< T > & );
for a particular type T such as float makes member function

C< float >::f5( X< float > & )
a friend function of only template class X< float >.
 Inside a class template for class X that has been declared with

template< class T > class X
a second class Y can be declared with 

friend class Y;
making every member function of class Y a friend of every template class produced from the class template for X.
Inside a class template for class X that has been declared with

template< class T > class X
a second class Z can be declared with
 
friend class Z< T >;
then when a template class is instantiated with a particular type for T such as float, all members of class Z< float > become friends of template class X< float >.
12.8 Templates and Static Members
What about static data members? Remember that with a non-template class, one copy of a static data member is shared among all objects of the class, and the static data member must be initialized at file scope.
Each template class instantiated from a class template has its own copy of each static data member of the class template; all objects of that template class share that one static data member. And as with static data members of non-template classes, static data members of template classes must be initialized at file scope.
Each template class gets its own copy of the class template's static member functions.
12.9 Summary
* Templates enable us to specify a range of related (overloaded) functions--called template functions--or a range of related classes--called template classes. * To use function templates, the programmer writes a single function template definition. Based on the argument types provided in calls to this function, C++ automatically generates separate functions to handle each type of call appropriately. These are compiled along with the rest of a program's source code. * All function template definitions begin with the keyword template followed by formal parameters to the * function template enclosed in angle brackets (< and >); each formal parameter must be preceded by the keyword class (or the new keyword typename). Keyword class used to specify function template type parameters means "any built-in type or user-defined type." * Template definition formal parameters are used to specify the types of the arguments to the function, the return type of the function, and to declare variables in the function. * The name of a formal parameter can be used only once in the parameter list of a template header. Formal parameter names among template functions need not be unique. * A function template itself may be overloaded in several ways. We can provide other function templates that specify the same function name but different function parameters. A function template can also be overloaded by providing other non-template functions with the same function name but different function parameters. * Class templates provide the means for describing a class generically and instantiating classes that are type- specific versions of this generic class. * Class templates are called parameterized types; they require type parameters to specify how to customize a generic class template to form a specific template class. * The programmer who wishes to use template classes * writes one class template. When the programmer needs a new type-specific class, the programmer uses a concise notation and the compiler writes the source code for the template class. * A class template definition looks like a conventional class definition except that it is preceded by template< class T > to indicate this is a class template definition with type parameter T indicating the type of the class to be created. The type T is mentioned throughout the class header and member function definitions as a generic type name. * The member function definitions outside the class template header each begin with the header template< * class T >. Then each function definition resembles a conventional function definition except that the generic data in the class is always listed generically as type parameter T. The binary scope resolution operator is used with the class template name to tie each member function definition to the class template's scope as in ClassName< T >. * It is possible to use non-type parameters in the header of a class template. * A class for a specific type can be provided to override the class template for that type. * A class template can be derived from a template class. A class template can be derived from a non-tem * plate class. A template class can be derived from a class template. A non-template class can be derived from a class template. * Functions and entire classes can be declared as friends of non-template classes. With class templates, the obvious kinds of friendship arrangements can be declared. Friendship can be established between a class template and a global function, a member function of another class (possibly a template class), or even an entire class (possibly a template class). * Each template class instantiated from a class template has its own copy of each static data member of the class template; all objects of that template class * share that one static data member. And as with static data members of non-template classes, static data members of template classes must be initialized at file scope. * Each template class gets a copy of the class template's static member functions.
Function templates, like macros, enable software reuse. But unlike macros, function templates help eliminate many types of errors because of the scrutiny of full C++ type checking.
This chapter does not contain any Portability tips.
This chapter does not contain any Applet Examples.
This chapter does not contain any Good Programming Practices tips.